第 374 场力扣周赛

需要添加的硬币的最小数量

题目

输入长度为 \(n\) 的数组 \(a\) 和整数 \(k\)，输出需要向数组插入多少个数，使得数组的子序列能够表示 \([1,k]\) 范围内的所有整数。

数据范围：\(1\leq n\leq 10^{5}\)，\(1\leq a_{i}\leq k\leq 10^{5}\)。

思路

从小到大遍历数组，假设当前能够表示的区间为 \([0,s]\)，此时遍历到数组中的数 \(a_{i}\)，我们可以表示区间 \([a_{i},s+a_{i}]\)。

• 如果 \(a_{i}\leq s+1\)，那么就可以合并两个区间，得到 \([0,s+a_{i}]\)，然后继续遍历 \(a_{i+1}\)。
• 否则，需要向数组插入数 \(s+1\) 来保证区间连续，得到 \([0,2s+1]\)，然后再次遍历 \(a_{i}\)。
• 不断重复上述过程直到能够表示区间 \([1,k]\)。

排序数组的时间复杂度为 \(O(n\log{n})\)，插入操作最多执行 \(O(\log{k})\) 次。

统计完全子字符串

题目

输入长度为 \(n\) 的由小写英文字母组成的字符串 \(s\) 和整数 \(k\)，输出满足以下两个条件的子字符串的个数。

• 每个字符恰好出现 \(k\) 次。
• 相邻字符在字母表中的距离小于等于 \(2\)。

数据范围：\(1\leq k\leq n\leq 10^{5}\)。

思路

距离大于 \(2\) 的相邻字符可以将字符串分割成若干子串，对于每个子串 \(t\) 考虑满足条件一的子串 \(t_{i}\) 个数即可。我们可以枚举 \(t_{i}\) 包含多少个不同的字符（设为 \(x\)），对于每个 \(x\) 使用滑动窗口可以得到 \(t\) 中满足条件一的长度为 \(kx\) 的子串个数。时间复杂度为 \(O(|\Sigma| n)\)，外层循环执行 \(O(|\Sigma|)\) 次，内层循环滑窗执行 \(O(n)\) 次，滑窗的同时使用计数数组统计有多少个字符恰好出现 \(k\) 次，判断的时间复杂度为 \(O(1)\)。

统计感冒序列的数目

题目

输入整数 \(n\) 和长度为 \(m\) 的按照升序排列的数组 \(a\)，数组 \(a\) 存储下标 \([0,n-1]\) 的子序列，输出所有不在数组 \(a\) 中的下标被选择的方案数，答案对 \(10^{9}+7\) 取余。下标 \(i\) 可以被选择，当且仅当下标 \(i-1\) 或者 \(i+1\) 被选择，数组 \(a\) 中的下标可以看作是被选择的。

数据范围：\(2\leq n\leq 10^{5}\)，\(1\leq m\leq n-1\)，\(0\leq a_{i}\leq n-1\)。

思路

数组 \(a\) 中的下标将 \([0,n-1]\) 划分为多个子数组，首先考虑每个子数组内部的方案数：最左和最右的子数组只存在一种选择方案，其他子数组存在 \(2^{x_{i}-1}\) 种选择方案，\(x_{i}\) 为该子数组的长度。然后考虑子数组之间的方案数，最初我们有 \(n-m\) 个位置可以放置下标，假设各个子数组的长度分别为 \(x_{0},x_{1},\dots,x_{k}\)，那么总共有 \(\prod_{i=0}^{k}{C(n-m-\sum_{j=0}^{i-1}{x_{j}},x_{i})}=\frac{(n-m)!}{\prod_{i=0}^{k}{x_{i}!}}\) 种放置方案。将两者相乘即可得到答案，计算过程需要使用逆元和快速幂。